package com.gitee.ywj1352.kaishi.数组和排序;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author wenjie.yang
 * @date 4/21/2020 2:04 PM
 */
public class 岛屿的最大面积 {

    public static void main(String[] args) {
        int[][] arr = { {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
                        {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                        {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
                        {0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
                        {0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
                        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
                        {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                        {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}};

        int i = maxAreaOfIsland(arr);
        System.out.println(i);
    }


    public static int maxAreaOfIsland(int[][] grid) {
        int max = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    int infected = infected(grid, i, j);
                    max = Math.max(infected, max);
                }
            }
        }
        return max;
    }

    public static int infected(int[][] grid, int r, int c) {
        int a = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(r);
        queue.add(c);
        while (!queue.isEmpty()) {
            Integer row = queue.poll();
            Integer column = queue.poll();
            int temp = grid[row][column];
            if (temp == 1) {
                grid[row][column] = 0;
                a++;
            }
            //上
            if (row > 0 && grid[row - 1][column] == 1) {
                queue.add(row - 1);
                queue.add(column);
            }
            //下
            if (row < grid.length - 1 && grid[row + 1][column] == 1) {
                queue.add(row + 1);
                queue.add(column);
            }
            //左
            if (column > 0 && grid[row][column - 1] == 1) {
                queue.add(row);
                queue.add(column - 1);
            }
            //右
            if (column < grid[0].length - 1 && grid[row][column + 1] == 1) {
                queue.add(row);
                queue.add(column + 1);
            }
        }
        return a;
    }
}
